package leecode.q704;

public class Solution {
    int res = -1;
    int[] nums;
    int target;

    public int search(int[] nums, int target) {
        this.nums = nums;
        this.target = target;
        findTarget(0, nums.length);
        return res;
    }

    private void findTarget(int start, int end) {
        int length = end - start;
        if (length <= 1) {
            if (nums[start] == target) {
                res = start;
            }
            return;
        }
        int mid = length / 2;
        if (nums[start + mid] < target) {
            findTarget(start + mid, end);
        } else if (nums[start + mid] > target) {
            findTarget(start, end - mid);
        } else {
            res = start + mid;
        }
    }
}
